
package arbre;

import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.ListIterator;
import java.util.Random;

/**
 * Représente l'arbre binaire.
 * 
 * 
 * @author David Bernard
 * @java 1.6
 * 
 * @param <E> le type de l'élément.
 */
public class ArbreBinaire<E extends Comparable<E>>
{
	private NoeudArbreBinaire<E> racine = null;

	/**
	 * Redistribue aléatoirement les éléments dans l'arbre.
	 */
	public void rebalancer()
	{
		Random lcg = new Random();
		ArrayList<E> list = new ArrayList<E>();
		int nb = 0;

		this.addToList(list);

		this.removeAll();

		while (list.size() > 0)
		{
			nb = lcg.nextInt(list.size());
			this.set(list.remove(nb));
		}
	}

	/**
	 * Vide l'arbre binaire.
	 */
	public void removeAll()
	{
		this.racine = null;
	}

	/**
	 * Retourne une collection des valeurs de l'arbre.
	 * 
	 * @return une collection des valeurs.
	 */
	public Collection<E> values()
	{
		List<E> values = new ArrayList<E>();

		this.addToList(values);

		return values;
	}

	/**
	 * Ajoute un élément à l'arbre.
	 * 
	 * @param element l'élément à ajouté.
	 */
	public void add(E element)
	{
		if (this.racine != null)
		{
			this.push(racine, element, false);
		}
		else
		{
			this.racine = new NoeudArbreBinaire<E>(element);
		}
	}

	/**
	 * Retourne une valeur selon la clé.
	 * 
	 * @param c la clé de l'élément.
	 * 
	 * @return la valeur le l'élément désiré ou null si introuvable.
	 */
	public E get(E c)
	{
		E out = null;
		if (this.racine != null)
		{
			out = this.racine.get(c);
		}

		return out;
	}
	
	/**
	 * Modifie la valeur d'un élément ou l'ajoute s'il n'existe pas.
	 * 
	 * @param element l'élément à modifié ou à ajouté.
	 */
	public void set(E element)
	{
		if (this.racine != null)
		{
			this.racine.set(element);
		}
		else
		{
			this.racine = new NoeudArbreBinaire<E>(element);
		}
	}
	
	/**
	 * Donne le nombre d'éléments dans un arbre.
	 * 
	 * @return le nombre d'éléments dans l'arbre.
	 */
	public int size()
	{
		int size = 0;
		if (this.racine != null)
		{
			size = this.racine.size();
		}

		return size;
	}

	int degree()
	{
		int out = 0;

		if (this.racine != null)
		{
			out += this.racine.degree();
		}

		return out;
	}

	void printValues()
	{
		System.out.println("VALUES");
		if (this.racine != null)
		{
			this.racine.printValues();
		}

	}

void addToList(Collection<E> list)
	{
		if (this.racine != null)
		{
			this.racine.addToList(list);
		}
	}

	void debalancer()
	{
		ArrayList<E> list = new ArrayList<E>();
		ListIterator<E> ite = null;

		this.addToList(list);

		this.removeAll();

		ite = list.listIterator();
		while (ite.hasNext())
		{
			this.add(ite.next());
		}
	}

	private void push(NoeudArbreBinaire<E> noeud, E element, boolean acceptDupl)
	{
		int diff = noeud.getElement().compareTo(element);
		NoeudArbreBinaire<E> temp = null;
		if (diff < 0)
		{
			temp = noeud.getDroite();
			if (temp == null)
			{
				noeud.setDroite(new NoeudArbreBinaire<E>(element));
			}
			else
			{
				this.push(temp, element, acceptDupl);
			}
		}
		else if (diff > 0)
		{
			temp = noeud.getGauche();
			if (temp == null)
			{
				noeud.setGauche(new NoeudArbreBinaire<E>(element));
			}
			else
			{
				this.push(temp, element, acceptDupl);
			}
		}
		else if (acceptDupl)
		{
			noeud.setElement(element);
		}
		else
		{
			throw new DuplicateItemException();
		}
	}

	/**
	 * Retourne vrai si l'arbre est vide.
	 * 
	 * @return vrai si l'arbre est vide.
	 */
	public boolean estVide()
	{
		return this.racine != null;
	}

	/**
	 * Enlève l'élément reçu en paramêtre.
	 * 
	 * @param element L'élement à supprimer.
	 */
	public void removeElement(E element)
	{
		// réf à obj
		NoeudArbreBinaire<E> courant = null;
		// réf au père de obj
		NoeudArbreBinaire<E> pere = null;
		// se rendre au plus grand a gauche réf au plus grand
		NoeudArbreBinaire<E> temp = null;
		// réf au père du plus grand
		NoeudArbreBinaire<E> pereTemp = null;

		if (this.racine != null)
		{
			// trouver courant, l'objet à enlever et son père
			courant = this.racine;
			pere = this.racine;

			while (courant != null && !courant.getElement().equals(element))
			{
				pere = courant;
				if (element.compareTo(courant.getElement()) < 0)
				{
					courant = courant.getGauche();
				}
				else
				{
					courant = courant.getDroite();
				}
			}
			// si l'objet à enlever est trouvé
			if (courant != null)
			{
				// si la branche gauche de courant est vide
				if (courant.getGauche() == null)
				{
					// si c’est la racine qu’il faut enlever
					if (courant == this.racine)
					{
						this.racine = this.racine.getDroite();
					}
					/*
					 * sinon changer la gauche ou la droite de père selon le cas
					 */
					else if (pere.getGauche() == courant)
					{
						/*
						 * la gauche de père pointe vers la droite de courant
						 */
						pere.setGauche(courant.getDroite());
					}
					else
					{
						/*
						 * la droite de père ponte vers la droite de courant
						 */
						pere.setDroite(courant.getDroite());
					}

				}
				/*
				 * sinon la branche gauche de l’élément à supprimer n’est pas
				 * vide
				 */
				else
				{
					temp = courant.getGauche();
					pereTemp = courant;

					while (temp.getDroite() != null)
					{
						pereTemp = temp;
						temp = temp.getDroite();
					}

					/*
					 * recopier la valeur de cet élément à la place de celui à
					 * supprimer
					 */
					courant.setElement(temp.getElement());

					/*
					 * ajuster les références en enlevant le plus grand si le
					 * plus grand est sous obj.
					 */
					if (courant.getGauche() == temp)
					{
						courant.setGauche(temp.getGauche());
					}
					else
					{
						pereTemp.setDroite(temp.getGauche());
					}
				}
			}
		}
	}
}
